package probleme_1;

import java.util.Random;
import java.util.ArrayList;

public class LinearSpacePerfectHashing<AnyType>
{
   static int p = 46337;
   
   QuadraticSpacePerfectHashing<AnyType>[] data;
   int a, b;
   
   LinearSpacePerfectHashing()
   {
      a=b=0; data = null;
   }
   
   LinearSpacePerfectHashing(ArrayList<AnyType> array)
   {
      AllocateMemory(array);
   }
   
   public void SetArray(ArrayList<AnyType> array)
   {
      AllocateMemory(array);	
   }
      
   @SuppressWarnings("unchecked")
   private void AllocateMemory(ArrayList<AnyType> array)
   {
      Random generator = new Random( System.nanoTime() );
      
      if(array == null || array.size() == 0)
      {
         a = b = 0;
         this.data = null;
         return;
      }
      if(array.size() == 1)
      {
         a = b = 0;
         this.data = (QuadraticSpacePerfectHashing<AnyType>[]) new QuadraticSpacePerfectHashing[1];
         data[0].SetArray(array);
         return;
      }
      
      a = generator.nextInt( p - 1 ) + 1;
      b = generator.nextInt( p );
      
      int m = array.size();
      data = (QuadraticSpacePerfectHashing<AnyType>[]) new QuadraticSpacePerfectHashing[ m ];
      
      ArrayList<ArrayList<AnyType>> al = new ArrayList<ArrayList<AnyType>>(m);
      
      for(int i=0; i<m; ++i)
         al.add(new ArrayList<AnyType>());
      
      // completer
      
      // On parcours tous les elements de array
      for(AnyType x : array){
    	  
    	  // On calcule l'index
    	  int index = ( (a*x.hashCode() + b ) % p ) % m;
    	  
    	  // On ajoute l'element dans l'ArrayList a l'index trouve
    	  al.get(index).add(x);	  
      }
      
      // Maintenant que tous les elements sont places, on tri chaque alveole de maniere quadratique
  
      // On parcours tous les elements de al (toutes les alveoles)
      for(int i=0; i<m; i++){
    	  
    	  // Si l'alveole contient des elements, on les tri de facon quadratique
	      if(al.get(i) != null){
	    	  data[i] = new QuadraticSpacePerfectHashing<AnyType>(al.get(i)); 
	      }
      }
   }
   
   public int Size()
   {
      if( data == null ) return 0;
      
      int size = 0;
      for(int i=0; i<data.length; ++i)
      {
         size += (data[i] == null ? 1 : data[i].Size());
      }
      return size;
   }
   
   public boolean contains(AnyType x )
   {
      if( Size() == 0 ) return false;
      
      int m = data.length;
      
      int index = ( ( a*x.hashCode() + b ) % p ) % m;
      
      index = ( index < 0 ? index + m : index );
      
      return ((data[index] != null) && (data[index].contains(x)));
   }
}
